1. Field of the Invention
The present invention relates to an image processing labelling circuit which, during the course of scanning two-valued pictures in one scene in raster scan direction with a specified mask, mainly recognizes the connectedness of an envisaged pixel and the pixels surrounding the envisaged pixel within the mask and sequentially determines and assigns a label value to each pixel. More particularly, the present invention relates to an image processing labelling circuit and labelling processor which provide the possibility of improving the processing speed and reducing the storage capacity of the working memory.
2. Description of the Prior Art
In recent years, the improvement in the processing capacity of digital processing devices such as micro processors (hereinafter called a MPU) and the like has led to automation in various fields, the automation making use of these digital processing devices.
For example, advanced image processing techniques, when applied to parts inspection in factories or hemocyte inspections and cytodiagnosis in the medical field, have led to automatic counting of the number of parts within a scene, the parts being part of the object of inspection, or to automatic counting of hemocytes and cells.
In order to count the objects in a specified picture, regions of, for example, black and white two-valued pictures contained in the picture must be recognized. To achieve this, the connectedness of each of the picture elements in the picture is evaluated, and for each region, which, for example, corresponds to the value black, labelling processing is performed.
The image processing labelling, which labels each region in a specified picture, provides the possibility of determining for each labelled region the area thereof, the length of the circumference thereof and the moment M and the angle .theta. principal axis thereof.
In general, the processing in an image processing labelling circuit, which labels each region in a specified picture in raster scan format, comprises the following three steps.
A. Temporary labelling. (Generation of the temporarily labelled image data and the temporary label table data, the latter indicating the conversion relations for the modification of the temporary labels.) PA1 B. Arrangement of the label table. PA1 C. Final labelling. (Generation of the finally labelled image data.)
A variety of such image processing labelling techniques have been disclosed.
For example, Japanese Patent Laid-Open Application 77687/1987 discloses a technique in which image data, such as temporarily labelled image data, in an image processing labelling circuit is composed of the coordinate data of the starting point of connected pixels which are to be labelled with one and the same label, the coordinate data of the end point of connected pixels and identification data, which holds the label value of the connected pixels.
According to the technique disclosed by Japanese Patent Laid-Open Application 77687/1987, it is possible to reduce the memory capacity of the working memory in the image processing labelling circuit.
Furthermore, Japanese Patent Laid-Open Application 29880/1990 discloses a technique which relates to the improvement of the temporary labelling processing (the improvement of temporary labelling algorithm), with the temporary labelling processing being performed for each pixel in a window consisting of 5 pixels. According to Japanese Patent Laid-Open Application 29880/1990, a scene comprising a plurality of pictures, each of which exists independently within the scene, is scanned using a window consisting of {(1.times.3)+(1.times.2)}=5 pixels, and an image processing labelling circuit performs temporary labelling in accordance with a plurality of classified window patterns while accessing a connection relation table.
The technique disclosed by Japanese Patent Laid-Open Application 29880/1990 provides the possibility of reducing the number of memory read and write accesses for the connection relation table memory, with the memory read and write accesses being performed each time one pixel is input when each pixel is labelled during the labelling of each region in a specified picture in raster scan format.
Furthermore, Japanese Patent Laid-Open Application 48778/1990 discloses a labelling technique that uses an ordinary two-valued mask consisting of an envisaged pixel and pixels adjacent to the envisaged pixel. The labelling is performed while making validity checks, by comparing the two-valued mask status of the run label, which represents the labels assigned to the adjacent runs, and, if a plurality of adjacent runs exist, of the connected label, which is the newest label among the adjacent run labels, in the initial label selection control portion. That is, according to this technique, labelling is performed while making validity checks for which not only the pixels in the mask, which consists of the envisaged pixel and pixels adjacent to the envisaged pixel, but also labels of pixels outside the mask are used.
According to Japanese Patent Laid-Open Application 48778/1990, during the initial labelling in the image processing labelling circuit, it is possible to prevent an overflow of the initial labels during the processing, the overflow resulting from a significant increase in the number of initial labels (types), and to prevent the load of the integration processing part from increasing, the object of the integration processing part being the mutual consolidation of the initial labels.
Furthermore, Japanese Patent Laid-Open Application 9478/1987 discloses a technique which allows the reduction of the number of times the working memory is accessed by using a mask of m.times.n pixels and by using a MAX-MIN format label relation table in the labelling processor, which performs the labelling of each region in a specified picture in raster scan format.
In the MAX-MIN format label relation table, the table addresses are conversion source label values, the table data is conversion target label values, and only table data, the value of which is smaller than the value of the corresponding table address, is written into the memory of each table address.
Also, in Japanese Patent Laid-Open Application 9478/1987, a label separation detection portion is provided. This label separation detection portion sets a separation detection flag, if it is detected that in a junction, where two connected pixels of different label values meet, the MAX and MIN of the MAX-MIN format label relation table are not equal. If the separation detection flag is set, repetition of the table conversion of the label relation table prevents one and the same object from being separated due to partially different labelling.
However, although Japanese Patent Laid-Open Application 77687/1987 provides the possibility of reducing the storage capacity of the working memory in an image processing labelling circuit when compared with conventional image processing labelling circuits, it is a problem that three types of data, namely the coordinate data of the starting point of the connected pixel, the coordinate data of the end point of the connected pixel and an identifier, which holds the label value of the connected pixel, must be stored for each connected pixel to which one and the same label is assigned.
For example, if the number of pixels per scene is 30.times.10=300, at least 5 bits are required to express the coordinates of the starting point and end point (the maximum value of the coordinates is 30) of the connected pixel to which one and the same label is assigned. Accordingly, if the memory, which stores the label value of the connected pixel, is an 8-bit memory, a storage element of a total of 18 bits is required for each connected pixel to which one and the same label is assigned.
Also, it is presumed that, in Japanese Patent Laid-Open Application 29880/1990, the storage of the labelling for each pixel is performed for each pixel, which has the disadvantage of taking up an enormous amount of working memory. If, for example, one label value is stored in an 8-bit memory element, and, if the number of pixels per scene is 30.times.10=300, then a working memory of a total of 2400 bits is required to store the label values of each pixel in the scene.
Also, in Japanese Patent Laid-Open Application 48778/1990, labelling is performed while checking the validity of the labelling for the envisaged pixel by comparing, during the labelling of the envisaged pixel, the two-valued mask status of the run label, which represents the labels assigned to the adjacent runs adjacent to the envisaged pixel, and, if a plurality of adjacent runs exist, of the connected label, which is the newest label among the adjacent run labels. Therefore, the labelling circuit is extremely complex, which causes a delay in the processing speed. Also, the verification of the correctness of this labelling circuit is supposed to be extremely difficult.
Furthermore, it is presumed that in Japanese Patent Laid-Open Application 9478/1987 the storage of the label value of each pixel is performed for each pixel. Therefore, as with the technique disclosed by Japanese Patent Laid-Open Application 29880/1990, there is the problem that the storage capacity of the working memory in the image processing labelling circuit tends to become large.
Also, in each of Japanese Patent Laid-Open Application 29880/1990 and Japanese Patent Laid-Open Application 9478/1987, there is a problem that, as shown in FIG. 19, many temporary label values occur, when each pixel in the portion indicated by the slant lines in FIG. 18 is being labelled, although the portion is a region to which one and the same label should be assigned. This results from the fact that only the temporary label values in the window, which consists of five pixels, are used as a condition for the determination of the label value (temporary label value) of the envisaged pixel, which assigns the temporary label.
Also, during the temporary labelling of each region of the picture shown in FIG. 21, a total of three junctions indicated by the numerals J1-J3 occur. This gives rise to a temporary labelling which uses many temporary labels, as illustrated in FIG. 21. Furthermore, the data of the MAX-MIN format label relation table at this time is such that label value 6 should be converted to label value 5, label value 4 should be converted to label value 2, label value 3 should be converted to label value 2 and label value 2 should be converted to label value 1. Hitherto, in order to complete such a label table arrangement, that is, for example, in order to convert all the label values 4, 3 and 2 into the label value 1, thus completing the arrangement of the label table, at least two table conversions had to be performed, which required a long processing time.